<?php
// 1.初始化、插入操作的时候，注意最后一个节点的指向，最后一个节点的 next 要指向第一个节点
// 2.判断链表遍历是否完成的条件为 item->next == head ，也就是说，判断这个节点的下一个节点如果是头节点的话，链表就遍历完成了。

// 节点类
class Node
{
    public $data;              // 节点数据
    public $previous = NULL;   // 前驱
    public $next = NULL;       // 后继

    public function __construct($data)
    {
        $this->data = $data;
        $this->previous = NULL;
        $this->next = NULL;
    }
}
// 双链表类
class DoubleLinkedList
{
    public $header;    // 头节点

    function __construct($data)
    {
        $this->header = new Node($data);
    }

    // 查找节点
    public function find($item)
    {
        $current = $this->header;
        while ($current->data != $item) {
            $current = $current->next;
        }
        return $current;
    }

    // 查找链表最后一个节点
    public function findLast()
    {
        $current = $this->header;
        while ($current->next != null) {
            $current = $current->next;
        }
        return $current;
    }

    /**
     * @description:（在节点后）插入新节点
     * @param {object} $item 当前节点
     * @param {string} $new 新节点
     * @return {bool}
     * @Author: zuoyi
     * @Date: 2022-05-12 10:41:32
     * @LastEditTime: Do not edit
     */    
    public function singleinsert($item, $new)
    {
        $newNode = new Node($new);
        $current = $this->find($item);
        $newNode->next = $current->next;
        $newNode->previous = $current;
        $current->next = $newNode;
        return true;
    }

    public function multInsert($data)
    {
        foreach ($data as $v) {
            $newNode = new Node($v);
            $newNode->next = $this->header->next;
            $newNode->previous = $this->header;
            $this->header->next = $newNode;
        }
    }

    // 从链表中删除一个节点
    public function delete($item)
    {
        $current = $this->find($item);
        if ($current->next != null) {
            $current->previous->next = $current->next;
            $current->next->previous = $current->previous;
            $current->next = null;
            $current->previous = null;
            return true;
        }
    }

    // 显示链表中的元素
    public function display()
    {
        return $this->header;
    }
    
    // 反序显示双向链表中的元素
    public function dispReverse()
    {
        $current = $this->findLast();
        while ($current->previous != null) {
            echo $current->data . "&nbsp;&nbsp;&nbsp";
            $current = $current->previous;
        }
    }
}

// 测试
$linkedList = new DoubleLinkedList('1');
// $linkedList->singleinsert('1', '2');
// $linkedList->singleinsert('2', '3');
// $linkedList->singleinsert('3', '4');

$linkedList->multInsert([2, 3, 4, 5]);

print_r($linkedList->display());

// $linkedList->delete('USA');

// $linkedList->display();
